/**
 * Binary Tree Maximum Path Sum
Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:
Given the below binary tree,

       1
      / \
     2   3
Return 6.
 */

package com.xinpan.exercise;


public class MaxPathSum {
    public int maxPathSum(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(root == null)
            return Integer.MIN_VALUE;
        
        History lHis = new History();
        History rHis = new History();
        
        maxSum(root.left, lHis);
        maxSum(root.right, rHis);
        
        int sum = root.val;
        if(lHis.add > 0) sum += lHis.add;
        if(rHis.add > 0) sum += rHis.add;

        return max(sum, lHis.max, rHis.max);
    }
    
    public void maxSum(TreeNode root, History his)
    {
        if(root == null)
        {
            his.max = Integer.MIN_VALUE;
            his.add = Integer.MIN_VALUE;
            return;
        }
        
        History lHis = new History();
        History rHis = new History();
        
        maxSum(root.left, lHis);
        maxSum(root.right, rHis);

        
        int sum = root.val;
        if(lHis.add > 0) sum += lHis.add;
        if(rHis.add > 0) sum += rHis.add;
        his.max = max(sum, lHis.max, rHis.max);
        
        
        int lAdd = root.val;
        int rAdd = root.val;
        if(lHis.add > 0) lAdd += lHis.add;
        if(rHis.add > 0) rAdd += rHis.add;

        his.add = max(lAdd, rAdd, root.val);
        if(his.add < 0)
            his.add = Integer.MIN_VALUE;
    }
    
    public int max(int a, int b, int c)
    {
        int max = a;
        if(b > max)
            max = b;
        if(c > max)
            max = c;
        return max;
    }
    
    class History
    {
        int max;
        int add;
    }
    
    class TreeNode {
   	 int val;
   	 TreeNode left;
   	 TreeNode right;
   	 TreeNode(int x) { val = x; }
   }
}
